Berlainan dengan Kerajaan-Kerajaan Melayu di Sumatera Timur lainnya, pemerintahan Kesultanan Deli bersifat federasi yang longgar sesuai dengan pepatah yang terdapat di Deli "Raja Datang, Orang Besar Menanti". Tuanku Panglima Gocah Pahlawan sebagai Raja Pertama di Tanah Deli yang dirujuk oleh Sultan Aceh sebagai wakilnya di Sumatera Timur atau Tanah Deli.

Sewaktu pemerintahan Panglima Peringgit (Raja Deli II), Deli mengisytiharkan kemerdekaannya dari Kesultanan Aceh pada tahun 1669 mengikuti jejak-jejak negeri pesisir, dan berhubungan dagang dengan VOC di Melaka. Pada masa pemerintahan Panglima Paderap (Raja Deli III) terjadi perluasan wilayah di pesisir pantai hingga Serdang dan Denai.

Menurut laporan Jhon Anderson yang berkunjung ke Deli pada tahun 1823, Sultan Amaluddin Mangendar (Sultan Deli VI) adalah penguasa Deli pertama yang bergelar "Sultan" setelah Deli ditawan Kesultanan Siak pada tahun 1814. Menurut laporan Jhon Anderson lagi, Sultan Deli dibantu oleh 8 orang menteri dimana Sultan berkuasa dalam soal perang, mengawal pemerintahan seharian, mengadili hal jenayah, dan lain-lain.

Mereka itu ialah :

• Nakhoda Ngah bergelar Timbal-Timbalu
• Wak-Wak
• Salim
• Tok Manis
• Dolah
• Wakil
• Penghulu Kampung

Di samping menteri–menteri, terdapat juga Syah Bandar (Hamad) yang menguruskan hubungan perdagangan dan biasanya dibantu seorang mata-mata (seorang wanita yang pandai bernama Encik Laut) yang bertugas memungut cukai. Kemudian ada lagi para pembesar diraja, penghulu, para panglima, dan mata-mata yang melaksanakan tugas sekiranya dikehendaki Sultan, serta pegawai istana yang mengirimkan surat ke berbagai kerajaan. Sekiranya Sultan mangkat, andaikata penggantinya masih muda, maka Tuan Haji Cut atau Kadi (ulama tertinggi) bertindak dan melaksanakan semua fungsi pemerintahan kerajaan. Di bidang agama Islam Tuan Haji Cut juga bertindak sebagai mufti kerajaan, kemudian di bawahnya ada bilal, imam, khalif, dan penghulu masjid. Merekalah yang menangani masalah yang berhubungan dengan keagamaan.